package org.tony.algorithms.sort;

import java.util.Random;

public class QuickSort
{
	static final Random	ran	= new Random();

	public void swap(int[] src , int srcIndex , int destIndex)
	{
		int temp = src[srcIndex];
		src[srcIndex] = src[destIndex];
		src[destIndex] = temp;
	}

	public int partition(int[] src , int begin , int end)
	{
		int index = begin + (ran.nextInt(end - begin + 1));
		int pivot = src[index];
		swap(src, index, end);
		for (int i = index = begin; i < end; i++)
		{
			if (src[i] < pivot)
			{
				swap(src, i, index++);
			}
		}
		swap(src, index, end);
		return index;
	}

	public void qsort(int[] src , int start , int end)
	{
		if (start < end)
		{
			int index = partition(src, start, end);
			qsort(src, start, index - 1);
			qsort(src, index + 1, end);
		}
	}

	public void qsort(int[] src)
	{
		qsort(src, 0, src.length - 1);
	}
}
